package top.fengleifeng.question;

import top.fengleifeng.util.ListNode;

/**
 * @author : fengelfeing
 * @version V1.0
 * @Project: leetcode-test
 * @Package : top.fengleifeng.question
 * @Description:
 * @Date: 2020年11月02日4:39 下午
 */
public class Num1367二叉树中的列表 {

    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode() {}
     *     ListNode(int val) { this.val = val; }
     *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */
    /**
     * Definition for a binary tree node. public class TreeNode { int val; TreeNode left; TreeNode right; TreeNode() {}
     * TreeNode(int val) { this.val = val; } TreeNode(int val, TreeNode left, TreeNode right) { this.val = val;
     * this.left = left; this.right = right; } }
     */
    class Solution {

        public boolean isSubPath(ListNode head, TreeNode root) {
            return checkRoot(root, head);
        }

        private boolean checkRoot(TreeNode root, ListNode head) {
            if (root == null) {
                return false;
            }
            if (root.val == head.val) {
                //判断接下来的是否相同
                boolean flag = checkEqual(root.left, head.next) || checkEqual(root.right, head.next);
                if (flag) {
                    return true;
                }
            }
            return checkRoot(root.left, head) || checkRoot(root.right, head);
        }

        private boolean checkEqual(TreeNode root, ListNode head) {
            if (head ==null){
                return true;
            }
            if(root==null){
                return false;
            }
            if(root.val==head.val){
               return checkEqual(root.left, head.next) || checkEqual(root.right, head.next);
            }else{
                return false;
            }
        }
    }
}
